//你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障
//碍的高度。 
//
// 对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线
//的长度： 
//
// 
// 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。 
// 在这条路线中，必须包含第 i 个障碍。 
// 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。 
// 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。 
// 
//
// 返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。 
//
// 
//
// 示例 1： 
//
// 
//输入：obstacles = [1,2,3,2]
//输出：[1,2,3,3]
//解释：每个位置的最长有效障碍路线是：
//- i = 0: [1], [1] 长度为 1
//- i = 1: [1,2], [1,2] 长度为 2
//- i = 2: [1,2,3], [1,2,3] 长度为 3
//- i = 3: [1,2,3,2], [1,2,2] 长度为 3
// 
//
// 示例 2： 
//
// 
//输入：obstacles = [2,2,1]
//输出：[1,2,1]
//解释：每个位置的最长有效障碍路线是：
//- i = 0: [2], [2] 长度为 1
//- i = 1: [2,2], [2,2] 长度为 2
//- i = 2: [2,2,1], [1] 长度为 1
// 
//
// 示例 3： 
//
// 
//输入：obstacles = [3,1,5,6,4,2]
//输出：[1,1,2,3,2,2]
//解释：每个位置的最长有效障碍路线是：
//- i = 0: [3], [3] 长度为 1
//- i = 1: [3,1], [1] 长度为 1
//- i = 2: [3,1,5], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线
//- i = 3: [3,1,5,6], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线
//- i = 4: [3,1,5,6,4], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线
//- i = 5: [3,1,5,6,4,2], [1,2] 长度为 2
// 
//
// 
//
// 提示： 
//
// 
// n == obstacles.length 
// 1 <= n <= 105 
// 1 <= obstacles[i] <= 107 
// 
// 👍 12 👎 0


package cn.db117.leetcode.solution19;

import java.util.Arrays;

/**
 * 1964.找出到每个位置为止最长的有效障碍赛跑路线.find-the-longest-valid-obstacle-course-at-each-position
 *
 * @author db117
 * @since 2021-08-09 10:40:14
 **/

public class Solution_1964 {
    public static void main(String[] args) {
        Solution solution = new Solution_1964().new Solution();

        System.out.println(Arrays.toString(solution.longestObstacleCourseAtEachPosition(new int[]{
                3, 1, 5, 6, 4, 2
        })));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {
            // 300 题差不多
            int len = obstacles.length;
            // 模拟栈
            int[] stack = new int[len];
            int[] ans = new int[len];
            int top = -1;
            for (int i = 0; i < len; i++) {
                if (top == -1 || obstacles[i] >= stack[top]) {
                    // 大于栈顶的值
                    top++;
                    stack[top] = obstacles[i];
                    ans[i] = top + 1;
                } else {
                    // 二分，找第一个大于当前值的位置
                    int bs = bs(stack, top, obstacles[i]);
                    stack[bs] = obstacles[i];
                    ans[i] = bs + 1;
                }
            }
            return ans;
        }

        private int bs(int[] arr, int right, int target) {
            int left = 0;
            while (left < right) {
                int mid = left + (right - left) / 2;

                if (arr[mid] <= target) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }

            return right;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}